"""
初始化一个 n×n 大小的矩阵 mat，然后模拟整个向内环绕的填入过程：

定义当前左右上下边界 left,right,top,bottom
初始值 num = 1，迭代终止值 target = n * n；
当 num <= target 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，
每次填入后：执行 num += 1：得到下一个需要填入的数字；

更新边界：例如从左到右填完后，上边界 top += 1，相当于上边界向内缩 1。
使用num <= target而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
最终返回 matrix 即可

"""


class Solution:
    def generateMatrix(self, n: int) -> [[int]]:
        l, r, t, b = 0, n - 1, 0, n - 1
        mat = [[0 for _ in range(n)] for _ in range(n)]
        num, tar = 1, n * n
        while num <= tar:
            for i in range(l, r + 1):  # 从左到右
                mat[t][i] = num
                num += 1
            t += 1  # 从左到右遍历完一层，top+1
            for i in range(t, b + 1):  # 从上到下
                mat[i][r] = num
                num += 1
            r -= 1  # 从上到下,right-1
            for i in range(r, l - 1, -1):  # 从右到左
                mat[b][i] = num
                num += 1
            b -= 1
            for i in range(b, t - 1, -1):  # 从下到上
                mat[i][l] = num
                num += 1
            l += 1
        return mat

    def generateMatrix2(self, n: int) -> [[int]]:
        mat = [[0] * n for _ in range(n)]
        start, end = 0, n - 1
        num = 1
        while start <= end:
            # 填充上边界
            for i in range(start, end + 1):
                mat[start][i] = num
                num += 1
            # 填充右边界
            for i in range(start + 1, end + 1):
                mat[i][end] = num
                num += 1
            # 填充下边界
            if start < end:  # 确保不是同一个单元格
                for i in range(end - 1, start - 1, -1):
                    mat[end][i] = num
                    num += 1
            # 填充左边界
            if start < end:  # 确保不是同一个单元格
                for i in range(end - 1, start, -1):
                    mat[i][start] = num
                    num += 1
            start += 1
            end -= 1

        # 如果 n 是奇数，填充中心元素
        if n % 2 == 1:
            mat[n // 2][n // 2] = num-1

        return mat


if __name__ == '__main__':
    sou = Solution()
    # print(sou.generateMatrix(3))
    # print(sou.generateMatrix(4))
    # [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
    print(sou.generateMatrix2(3))
    # print(sou.generateMatrix2(4))
    # [[1, 2, 3], [8, 10, 4], [7, 6, 5]]
